from tools_algorithm import *


# 1964. 找出到每个位置为止最长的有效障碍赛跑路线
class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        limit = max(obstacles) + 1
        s = [0] * limit

        def find(o):
            mx = 0
            while o > 0:
                mx = max(mx, s[o])
                o -= o & -o
            return mx

        def update(o, c):
            while o < limit:
                s[o] = max(s[o], c)
                o += o & -o

        ans = []
        for o in obstacles:
            c = find(o) + 1
            update(o, c)
            ans.append(c)
        return ans


# f = test_file_path(__file__)
# c = []
# for _ in range(10**5):
#     c.append(random.randint(1, 10**7))
# print(c, file=f)
c = [0, 0, 0]
c[1] = 1
c[1] = 2
print(c)
